import math
import matplotlib.pyplot as plt

def bresenham(x0, y0, x1, y1):
    points = []  # 存储直线上的点
    dx = abs(x1 - x0)
    dy = abs(y1 - y0)
    sx = 1 if x0 < x1 else -1
    sy = 1 if y0 < y1 else -1
    err = dx - dy

    while True:
        points.append((x0, y0))  # 记录当前点
        if x0 == x1 and y0 == y1:
            break
        e2 = 2 * err
        if e2 > -dy:
            err -= dy
            x0 += sx
        if e2 < dx:
            err += dx
            y0 += sy

    return points

def find_boundary_intersection(x0, y0, angle, width, height):
    """
    计算从点 (x0, y0) 出发，按给定角度延伸的直线与矩形边界的第一个交点
    :param x0: 起点的 x 坐标
    :param y0: 起点的 y 坐标
    :param angle: 直线的角度（以度数表示，0° 为水平向右，正数为逆时针）
    :param width: 矩形的宽度
    :param height: 矩形的高度
    :return: 第一个交点的坐标（不包括起点本身）
    """
    # 计算方向向量
    dx = math.cos(math.radians(angle))
    dy = math.sin(math.radians(angle))

    # 存储交点
    intersections = []

    # 检查与左边界 (x = 0) 的交点
    if dx != 0:  # 避免平行于 y 轴
        t_left = -x0 / dx
        y_left = y0 + t_left * dy
        if 0 <= y_left <= height:  # 确保交点在矩形范围内
            if not (x0 == 0 and y0 == y_left):  # 避免起点本身
                intersections.append((0, y_left, t_left))  # 添加 t 参数用于排序

    # 检查与右边界 (x = width) 的交点
    if dx != 0:  # 避免平行于 y 轴
        t_right = (width - x0) / dx
        y_right = y0 + t_right * dy
        if 0 <= y_right <= height:  # 确保交点在矩形范围内
            if not (x0 == width and y0 == y_right):  # 避免起点本身
                intersections.append((width, y_right, t_right))  # 添加 t 参数用于排序

    # 检查与下边界 (y = 0) 的交点
    if dy != 0:  # 避免平行于 x 轴
        t_bottom = -y0 / dy
        x_bottom = x0 + t_bottom * dx
        if 0 <= x_bottom <= width:  # 确保交点在矩形范围内
            if not (x0 == x_bottom and y0 == 0):  # 避免起点本身
                intersections.append((x_bottom, 0, t_bottom))  # 添加 t 参数用于排序

    # 检查与上边界 (y = height) 的交点
    if dy != 0:  # 避免平行于 x 轴
        t_top = (height - y0) / dy
        x_top = x0 + t_top * dx
        if 0 <= x_top <= width:  # 确保交点在矩形范围内
            if not (x0 == x_top and y0 == height):  # 避免起点本身
                intersections.append((x_top, height, t_top))  # 添加 t 参数用于排序

    # 过滤掉 t <= 0 的交点
    intersections = [p for p in intersections if p[2] > 0]

    # 按 t 参数（方向）进行排序，并返回第一个交点
    intersections = sorted(intersections, key=lambda p: p[2])

    # 返回第一个交点的坐标（去掉 t 参数）
    return (intersections[0][0], intersections[0][1]) if intersections else None

def draw_line_to_boundary(x0, y0, angle, width, height):
    # 找到终点
    end_point = find_boundary_intersection(x0, y0, angle, width-1, height-1)
    if end_point is None:
        return []  # 没有交点，返回空
    x1, y1 = end_point
    x1 = int(x1)
    y1 = int(y1)

    # 使用 Bresenham 算法绘制直线
    return bresenham(x0, y0, x1, y1)

def visualize_line(x0, y0, angle, width, height):
    # 获取直线上的点
    line_points = draw_line_to_boundary(x0, y0, angle, width, height)
    line_points1 = draw_line_to_boundary(x0, y0, -1 * angle, width, height)
    line_points =  line_points + line_points1
    # 提取 x 和 y 坐标
    # x_coords1, y_coords1 = zip(*line_points)
    x_coords, y_coords = zip(*line_points)
    # x_coords = tuple(int(width / 2) - y for y in y_coords1)
    # y_coords = tuple(int(height) - x for x in x_coords1)

    # 绘制图像
    plt.figure(figsize=(8, 8))
    plt.plot(x_coords, y_coords, marker='o', color='blue', label='Bresenham Line')  # 正常绘制 X 和 Y
    # plt.scatter([x0], [y0], color='red', label='Start Point')  # 起始点保持正常顺序
    # plt.scatter([x0], [y0], color='red', marker='s', label='Start Point')  # 使用方形标记
    plt.scatter([x0], [y0], color='red', marker='s', s=200, label='Start Point')  # 使用更大的方形标记


    plt.xlim(0, width)   # X 轴范围为宽度
    plt.ylim(0, height)  # Y 轴范围为高度
    plt.gca().invert_yaxis()  # 反转 Y 轴
    plt.grid(True)
    plt.legend()
    plt.title(f"Bresenham Line (Angle: {angle}°)")
    plt.xlabel("X")  # X 轴标签为正常的 X
    plt.ylabel("Y")  # Y 轴标签为正常的 Y
    plt.savefig("plot.png")  # 保存图像
    # plt.show()  # 显示图像



# 测试：从点 (50, 50) 出发，角度为 30 度，屏幕大小为 100x100
if __name__ == '__main__':
    x, y = 20, 40
    # x1 = 
    # y1 = 
    # visualize_line(x, y, 30, 100, 100)
    # 示例
    width = 200  # 矩形宽度
    height = 200  # 矩形高度
    x0, y0 = 2, 100  # 起点
    angle = 45  # 角度（以度数表示）

    intersections = find_boundary_intersection(x0, y0, angle, width, height)
    print("交点坐标:", intersections)
    intersections = find_boundary_intersection(x0, y0, angle * -1, width, height)
    print("交点坐标:", intersections)